The use of a global positioning system (GPS) to determine the location of people and objects is becoming wide spread. Automobiles, wireless telephones and other devices are being designed to include global positioning system receivers. These receivers are used to receive signals from satellites. These received signals provide information that allows the receiver to determine the receiver's location on earth with relatively great accuracy. The signals that are received from the satellites are typically rather weak. Therefore, in order to determine the position of the receiver, the receiver must be sufficiently sensitive to receive these weak signals and interpret the information that is represented by them.
In accordance with the format that is used for one such GPS, the signals transmitted by each satellite are encoded to distinguish the signals transmitted by one satellite from the signals transmitted by the other satellites in the system. The codes that are assigned to each satellite are selected such that the receiver can apply a received signal that includes a signal transmitted from a particular satellite and a particular code associated with the particular satellite to a "correlator" and have only the energy of the signal that is encoded with that particular code emerge from the correlator.
FIG. 1 is an illustration of the timing of a portion of a signal 101 transmitted from a global positioning satellite, such as those in common use today. The transmitted signal 101 shown in FIG. 1 is encoded with a particular code having a duration of 1 millisecond (i.e., the "code period"). The signal is modulated with the code (i.e., the code and the information signal to be transmitted are logically exclusively ORed) every code period. Initially, the receiver determine whether a signal being transmitted from a particular satellite is being received. This is commonly referred to as "acquiring" a satellite. This is done by attempting to "correlate" the received signal with the code associated with that particular satellite (i.e., inputting the received signal and the particular code to the correlator to see if any of the energy in the received signal was encoded with the particular code). In order for the input signal and the code to be correlated, the code period of the signal being received and the code to which the received signal is being compared must be very closely aligned in time. FIG. 1 shows three attempts to correlate the received signal 101 with a code associated with a particular satellite. In the first attempt, the code 102a starts after the beginning of the code period 103 of the received signal 101. Therefore, this first attempt to correlate the received signal with the particular code will fail.
In a second attempt to correlate the received signal 101 with the particular code 102b (which has the same value as the code 102a, but is shifted in time), the code is shifted to a point later in time with respect to the beginning of the code period 103. However, the beginning of the code period of the received signal and the beginning of the code 102 are still not aligned. Therefore, even though the correct code is being compared to the received signal, the timing is not aligned. Accordingly, the attempt to correlate the received signal with the particular code fails again.
In the third attempt, the beginning of the code 102c is aligned with the beginning of a code period 103. The particular code is the same as the code with which the received signal was encoded and the code period 104 is aligned with the code 102c. Therefore, the correlation between the particular code and the received signal will be successful, assuming that the signal that was encoded with the particular code is being received with sufficient strength to allow the correlation to be detected.
However, in many cases, the signal being transmitted from a satellite is not sufficiently strong. This may be due to the fact that the amount of interference is too great or the signal is attenuated by obstructions, such as buildings, foliage, etc. Therefore, the correlation may not be detected, even when the timing is correct and the correct code is selected.
One way that has been proposed for improving the sensitivity of the receiver is to add the power that is transmitted in several code periods together and then attempt to correlate the sum of these code periods with the particular code of interest. In addition to the lack of sensitivity, the time at which the code periods begin is not known. Therefore, the same searching function must be performed as was illustrated in FIG. 1 and described in the accompanying text. This searching requires a relatively large amount of time.
One method that has been proposed for dealing with the amount of time required to determine the alignment of the code periods requires that several samples be taken for a number of "code sample periods". A code sample period is a period of time that is equal in duration to the code period, but which may not be aligned to a code period. The same number of samples are taken for each code sample period (e.g., 1 millisecond). Corresponding samples from each of these 1 millisecond code sample periods are then summed together to form a composite code sample period of 1 millisecond. FIG. 3 is an illustration of four code periods 301, 302, 303, 304 that are sampled 15 times each. The 15 samples from each of the four code periods 301, 302, 303, 304 are summed to form a composite code sample period 305. It should be understood that each such period 301, 302, 303, 304 must begin an integer number of code periods apart and preferably each such period is adjacent in time to one of the other such periods to form a contiguous stream of samples.
The composite code sample period is then transformed from the time domain to the frequency domain. That is, a time domain to frequency domain transform, such as a Fourier transform, is performed on the samples that make up the composite code sample period. The frequency domain result is then multiplied by a frequency domain representation of the particular code to which the received signal is to be correlated. A transform from the frequency domain to the time domain, such as an inverse Fourier transform, is then performed on this product. The time domain result provides an indication as to relative time difference between the beginning of the code sample periods and the beginning of the actual code periods of the received signal, assuming that the received signal has sufficient energy which has been encoded with the particular code.
One problem with this approach is that the information that is represented by the received signal, changes the state of the received signal at regular intervals which are several times longer than the code period. For example, in the GPS system commonly used in the United States, the content of a signal transmitted from a satellite has a bit length of 20 code periods (i.e., 20 ms). This has the effect of potentially inverting the state of the energy that is represented by the codes every 20 milliseconds. FIG. 2 illustrates the timing of a bit with respect to a code period. If energy in the signal received during a code period when the bit value is equal to a logical "one" is added to the energy received when the bit value is equal to a logical "zero", the total energy will be equal to zero. Therefore, "bit boundaries" 201 must be known in order to sum the energy of more than one code period. In addition, if the clock (oscillator) that is used to determine when to take the samples from each code sample period is not extremely stable, then the correlation will not be very good in the frequency domain. This will result in a loss of sensitivity, since the composite code sample period will not correlate well with the particular code of interest.
The present invention provides a method and apparatus which increases the sensitivity of a GPS receiver with less need for an extremely stable clock than is required in the case in which composite code samples periods are generated. In addition, the present invention provides a method for determining the location of bit boundaries within the received signal.